# 22. 括号生成

def generateParenthesis(n):

    result = []
    temp = []

    def trackback(a, b):
        if len(temp) == 2 * n:
            num = []
            if temp[0] != ')':
                num.append(temp[0])
                judge = True
                for s in range(1, len(temp)):
                    if temp[s] == '(':
                        num.append(temp[s])
                    else:
                        if num == []:
                            judge = False
                            break
                        else:
                            num.pop()
                if num == [] and judge == True:
                    result.append("".join(temp[:]))

        if a > 0:
            temp.append(')')
            trackback(a - 1, b)
            temp.pop()
        if b > 0:
            temp.append('(')
            trackback(a, b - 1)
            temp.pop()

    trackback(n, n)
    return result

if __name__ == "__main__":
    n = 3
    print(generateParenthesis(n))